﻿#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

//跳台阶扩展问题（规律）
//https://www.nowcoder.com/practice/953b74ca5c4d44bb91f39ac4ddea0fee?tpId=230&tqId=39750&ru=/exam/oj

//1.动态规划


//void func(int n)
//{
//    int dp[25] = {0};
//    dp[1]=1;
//
//    for (int i = 2; i <= n; i++)
//    {
//        for (int prev = 1; prev <= i - 1; prev++)
//            dp[i] += dp[prev];
//        dp[i]++;
//    }
//    cout << n << ": " << dp[n] << endl;
//}

//2.规律 dp[n]=2^(n-1)
//int main()
//{
//	int n;
//	cin >> n;
//	cout << (1 << (n - 1)) << endl;
//	return 0;
//}

//int main() {
//    //cin >> n;
//    for (int i = 1; i < 10; i++)
//        func(i);
//}


// 包含不超过两种字符的最⻓⼦串（滑动窗⼝）
// https://www.nowcoder.com/practice/90d6a362fa7d4c519d557da797bb02ce?tpId=196&tqId=40552&ru=/exam/oj

//#include <iostream>
//#include <string>
//using namespace std;
//
//int main() {
//    string s;
//    cin >> s;
//
//    int left = 0, right = 0;
//    int hash[26] = { 0 };//统计窗口中每种字符个数
//    int cnt = 0;//窗口中字符种类数
//    int ret = 0;
//
//    while (right < s.size())
//    {
//        if (hash[s[right] - 'a']++ == 0)//窗口中没有这种字符
//            cnt++;
//        while (cnt > 2)
//        {
//            if (--hash[s[left++] - 'a'] == 0)//窗口少一种字符
//                cnt--;
//        }
//        ret = max(right - left + 1, ret);
//        right++;
//    }
//    cout << ret;
//}


//JZ38 字符串的排列
//https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&ru=/exam/oj

//class Solution {
//public:
//    vector<string> vs;
//    string path;
//    int vis[11] = { 0 };
//
//    void dfs(int floor, string& s)    {
//        if (floor == s.size())
//        {
//            vs.push_back(path);
//            //cout << path << endl;
//            return;
//        }
//
//        for (int i = 0; i < s.size(); i++)
//        {
//            if (!vis[i])
//            {
//                //剪枝 跳过重复字母
//                if (i > 0 && s[i] == s[i - 1] && !vis[i - 1]) continue;
//                vis[i] = 1;
//                path += s[i];
//                dfs(floor + 1, s);
//                path.pop_back();
//                vis[i] = 0;
//            }
//        }
//    }
//
//    vector<string> Permutation(string str) {
//        sort(str.begin(), str.end());
//        dfs(0, str);
//        return vs;
//    }
//};
//
//int main()
//{
//    Solution s;
//    s.Permutation("aa");
//}